package com.duoduo.动态规划;

/**
 * @program: algorithm
 * @description: 最大子数组和53
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 *
 * 子数组 是数组中的一个连续部分。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出：6
 * 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
 * @author: chaidl  ！
 * @create: 2022-05-02 23:43
 */
public class 最大子数组和53 {
	public static void main(String[] args) {
		int[] dp=new int[] {-2,1,-3,4,-1,2,1,-5,4};
		maxSubArray(dp);
	}
	public static int maxSubArray2(int[] nums) {
		/**
		* 生成nums的最大子数组和
		*/
		int max = nums[0];
		int sum = 0;
		for (int i = 0; i < nums.length; i++) {
			//如果和小于等于0，则可以把这个数之前的数据全部抹去从当前数字开始计算
			if (sum <= 0) {
				sum = nums[i];
			} else {
				sum += nums[i];
			}
			max = Math.max(max, sum);
		}
		return max;
	}
	public static int maxSubArray(int[] nums) {
		//初始化第一个值和最大值
		int pre = 0, maxAns = nums[0];
		for (int x : nums) {
			pre = Math.max(pre + x, x);
			maxAns = Math.max(maxAns, pre);
		}
		return maxAns;
	}
	
	public int maxSubArray1(int[] nums) {
		//新数组
		int[] dp=new int[nums.length];
		//新数组的第一个元素和老数组一样
		dp[0]=nums[0];
		//刚开始最大元素就是第一个数字
		int result=dp[0];
		for (int i = 1; i < nums.length; i++) {
			//如果新数组的上一个元素和当前元素相加以后和当前元素比较大小
			//也就是-2+1和1比较大小
			dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
			//如果当前元素大于最大值，就将最大值改为当前元素
			if (dp[i]>result){
				result = dp[i];
			}
		}
		return result;
	}
}
